# 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
#
# 你可以按 任何顺序 返回答案。
#
# 示例 1:
# 输入：n = 4, k = 2
# 输出：
# [
#   [2,4],
#   [3,4],
#   [2,3],
#   [1,2],
#   [1,3],
#   [1,4],
# ]

# 示例 2:
# 输入：n = 1, k = 1
# 输出：[[1]]
from typing import List


class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        ress = list[List[int]]()

        def recur(index: int, tmp_res: List[int]) -> None:
            if len(tmp_res) > k or len(tmp_res) + (n - index + 1) < k:
                return
            if index == n + 1:
                ress.append(tmp_res[:])
                return

            # 选择当前元素
            tmp_res.append(index)
            recur(index + 1, tmp_res)
            tmp_res.pop()
            # 不选择当前元素
            recur(index + 1, tmp_res)

        recur(1, [])
        return ress


if __name__ == "__main__":
    n, k = 4, 2
    print(Solution().combine(n, k))
